home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / a_utils / decomp.lha / decomp / hier.c < prev    next >
C/C++ Source or Header  |  1988-01-12  |  21KB  |  924 lines
  1. /*
  2.  * Module: hier.c
  3.  *
  4.  * Author: J. Reuter
  5.  *
  6.  * This module converts a directed graph of basic blocks into
  7.  * a tree of generic control constructs.  It is based on the
  8.  * Unix "struct" program (which is poorly commented, so this is
  9.  * too).
  10.  */
  11.  
  12. #include "defs.h"
  13. #include "nodes.h"
  14.  
  15. #define CHILDNUM(v)    (node_info[node_array[v]->node_type].num_children)
  16.  
  17. struct hierarchy {
  18.     int h_after;        /* node numbers associated with after numbers*/
  19.     int h_ntobef;        /* before numbers associated with nodes */
  20.     int h_ntoaft;        /* after numbers associated with nodes */
  21.     int h_head;
  22.     struct list *h_inarc;
  23.     int h_dom;
  24. };
  25.  
  26. #define after(n) (h[n].h_after)
  27. #define ntobef(n) (h[n].h_ntobef)
  28. #define ntoaft(n) (h[n].h_ntoaft)
  29. #define head(n) (h[n].h_head)
  30. #define inarc(n) (h[n].h_inarc)
  31. #define dom(n) (h[n].h_dom)
  32.  
  33. struct hierarchy *h;        /* where we allocate the hierarchy structure */
  34.  
  35. struct list {
  36.     int element;
  37.     struct list *next_list;
  38. };
  39.  
  40. struct list *consls();
  41. struct node *get_orif();
  42.  
  43. int access_count;        /* number of nodes accessible from start */
  44. static int exit_size = 0;    /* threshold for loop inclusion of small
  45.                    exit code */
  46.  
  47. hier()
  48. {
  49.     register int v;
  50.  
  51.     /* find back edges, unreachable nodes */
  52.     dfs();
  53.  
  54.     /* sets head(v) to N_ITER heading smallest loop containing v or NONE */
  55.     gethead();
  56.  
  57.     /* sets inarc(v) to list of forward arcs entering v */
  58.     getinarc();
  59.  
  60.     /* sets dom(v) to immediate dominator of v or NONE */
  61.     getdom();
  62.  
  63.     /* build the tree structure using head, inarc, dom */
  64.     gettree();
  65.  
  66.     for (v = 0; v < node_count; v++) {
  67.     freelst( inarc(v) );
  68.     inarc(v) = 0;
  69.     }
  70.     free( h );
  71. }
  72.  
  73. #define UNSEEN 0
  74. #define STACKED 1
  75. #define FINISHED 2
  76.  
  77. /*
  78.  * depth-first search used to identify back edges, unreachable nodes;
  79.  * each node v entered by back edge replaced by
  80.  * N_LOOP ->N_ITER -> v,
  81.  * so that back edges entering v now enter the N_ITER,
  82.  * and other edges entering v now enter the N_LOOP.
  83.  * Nodes are numbered according to depth-first search:
  84.  *      before numbering- ntobef(v) = i => node numbered v is i'th
  85.  *        node in order of first visit during the search;
  86.  *    after numbering- ntoaft(v) = i => node numbered v is i'th
  87.  *        node visited in order of last visit during the search.
  88.  *        Also, in this case after(i) = v.
  89.  */
  90.  
  91. static int befcount, aftcount;
  92.  
  93. /* following defines used to mark back edges and nodes entered by back edges */
  94.  
  95. #define mark(n)        n->reach = 1; /* mark node n */
  96. #define unmark(n)    n->reach = 0;
  97. #define marked(n)    (n->reach == 1)
  98. #define mark_edge(e)    if ((e)>-1) (e) = -2-(e); /* mark edge e */
  99. #define unmark_edge(e)    if ((e)<-1) (e) = -2-(e);
  100. #define marked_edge(e)    ((e) < -1)
  101.  
  102.  
  103. static
  104. dfs()        /* depth first search */
  105. {
  106.     register int i;
  107.     register int w;
  108.  
  109.     for ( w = 0; w < node_count; w++ ) {
  110.     node_array[w]->node_scratch = UNSEEN;
  111.     node_array[w]->reach = 0; /* use reach to count inarcs */
  112.     }
  113.  
  114.     if_inarcs( 0 );
  115.  
  116.     for ( w = 0; w < node_count; w++ )
  117.     node_array[w]->node_scratch = UNSEEN;
  118.  
  119.     compound_if( 0 );
  120.  
  121.     access_count = 0;
  122.     for ( w = 0; w < node_count; w++ ) {
  123.     node_array[w]->node_scratch = UNSEEN;
  124.     unmark( node_array[w] );
  125.     }
  126.  
  127.     search( 0 );
  128.  
  129.     unreach();
  130.  
  131.     addloop();
  132.  
  133.     h = (struct hierarchy *) malloc( node_max * sizeof( struct hierarchy ) );
  134.     if ( h == NULL ) {
  135.     fprintf( stderr, "Out of memory\n" );
  136.     exit( 1 );
  137.     }
  138.  
  139.     for (i = 0; i < access_count; ++i)
  140.     after(i) = NONE;
  141.  
  142.     for (w = 0; w < node_count; ++w)
  143.     ntobef(w) = ntoaft(w) = NONE;
  144.  
  145.     befcount = 0;
  146.     aftcount = 0;
  147.  
  148.     repsearch(0);
  149. }
  150.  
  151. /*
  152.  * compound_if converts complex branch logic into compound if statements.
  153.  * Only N_ORIFs are generated here.  Boolean logic will later convert
  154.  * negated N_ORIFs into N_ANDIFs.
  155.  * In addition, each N_CASE node is nested within a N_SWITCH node to
  156.  * allow for proper nesting of case bodies and case labels are added.
  157.  */
  158.  
  159. /* first count inarcs */
  160. static
  161. if_inarcs( v )
  162. register int v;
  163. {
  164.     register struct node *n;
  165.     register int i, adj;
  166.  
  167.     n = node_array[v];
  168.     n->node_scratch = STACKED;
  169.  
  170.     for ( i = 0; i < n->num_arcs; i++ ) {
  171.     adj = n->arcs[i];
  172.     node_array[adj]->reach++;
  173.     if ( node_array[adj]->node_scratch == UNSEEN )
  174.         if_inarcs( adj );
  175.     }
  176.     n->node_scratch = FINISHED;
  177. }
  178.  
  179. /* now collapse if's */
  180. /* reach contains inarc count for node */
  181. static
  182. compound_if( v )
  183. register int v;
  184. {
  185.     register int i;
  186.     register int adj;
  187.     register struct node *m, *n, *new;
  188.  
  189.     n = node_array[v];
  190.     n->node_scratch = STACKED;
  191.  
  192.     for ( i = 0; i < n->num_arcs; i++ ) {
  193.     adj = n->arcs[i];
  194.     if ( node_array[adj]->node_scratch == UNSEEN )
  195.         compound_if( adj );
  196.     }
  197.  
  198.     if ( n->node_type == N_IF || n->node_type == N_ORIF ) {
  199.  
  200.     m = node_array[ n->arcs[THEN_ARC] ];
  201.     if ( ( m->node_type == N_IF || m->node_type == N_ORIF ) &&
  202.         m->node_scratch == FINISHED && m->reach == 1 )
  203.  
  204.         if ( m->arcs[THEN_ARC] == n->arcs[ELSE_ARC] ) {
  205.         new = get_orif( v, TRUE, n->arcs[THEN_ARC], FALSE,
  206.                  n->arcs[ELSE_ARC], m->arcs[ELSE_ARC] );
  207.         i = m->arcs[THEN_ARC];
  208.         new->reach = n->reach;
  209.         m->arcs[THEN_ARC] = NONE;
  210.         m->arcs[ELSE_ARC] = NONE;
  211.         n->arcs[THEN_ARC] = NONE;
  212.         n->arcs[ELSE_ARC] = NONE;
  213.         node_array[v] = new;
  214.         node_array[node_count - 1] = n;
  215.         node_array[i]->reach--;
  216.         compound_if( v );
  217.         goto skip_else;
  218.  
  219.         } else if ( m->arcs[ELSE_ARC] == n->arcs[ELSE_ARC] ) {
  220.         new = get_orif( v, TRUE, n->arcs[THEN_ARC], TRUE,
  221.                  n->arcs[ELSE_ARC], m->arcs[THEN_ARC] );
  222.         i = m->arcs[ELSE_ARC];
  223.         new->reach = n->reach;
  224.         m->arcs[THEN_ARC] = NONE;
  225.         m->arcs[ELSE_ARC] = NONE;
  226.         n->arcs[THEN_ARC] = NONE;
  227.         n->arcs[ELSE_ARC] = NONE;
  228.         node_array[v] = new;
  229.         node_array[node_count - 1] = n;
  230.         node_array[i]->reach--;
  231.         compound_if( v );
  232.         goto skip_else;
  233.         }
  234.  
  235.     m = node_array[ n->arcs[ELSE_ARC] ];
  236.     if ( ( m->node_type == N_IF || m->node_type == N_ORIF ) &&
  237.         m->node_scratch == FINISHED && m->reach == 1 )
  238.  
  239.         if ( m->arcs[THEN_ARC] == n->arcs[THEN_ARC] ) {
  240.         new = get_orif( v, FALSE, n->arcs[ELSE_ARC], FALSE,
  241.                  n->arcs[THEN_ARC], m->arcs[ELSE_ARC] );
  242.         i = m->arcs[THEN_ARC];
  243.         new->reach = n->reach;
  244.         m->arcs[THEN_ARC] = NONE;
  245.         m->arcs[ELSE_ARC] = NONE;
  246.         n->arcs[THEN_ARC] = NONE;
  247.         n->arcs[ELSE_ARC] = NONE;
  248.         node_array[v] = new;
  249.         node_array[node_count - 1] = n;
  250.         node_array[i]->reach--;
  251.         compound_if( v );
  252.  
  253.         } else if ( m->arcs[ELSE_ARC] == n->arcs[THEN_ARC] ) {
  254.         new = get_orif( v, FALSE, n->arcs[ELSE_ARC], TRUE,
  255.                  n->arcs[THEN_ARC], m->arcs[THEN_ARC] );
  256.         i = m->arcs[ELSE_ARC];
  257.         new->reach = n->reach;
  258.         m->arcs[THEN_ARC] = NONE;
  259.         m->arcs[ELSE_ARC] = NONE;
  260.         n->arcs[THEN_ARC] = NONE;
  261.         n->arcs[ELSE_ARC] = NONE;
  262.         node_array[v] = new;
  263.         node_array[node_count - 1] = n;
  264.         node_array[i]->reach--;
  265.         compound_if( v );
  266.         }
  267.  
  268.     } else if ( n->node_type == N_CASE ) {
  269.     /* add a N_SWITCH node for proper case stmt nesting */
  270.     if ( node_count + n->num_arcs > node_max )
  271.         node_grow();
  272.     new = get_node( 2 );
  273.     new->node_type = N_SWITCH;
  274.     new->start_address = n->start_address;
  275.     new->end_address = n->end_address;
  276.     new->num_arcs = 2;
  277.     new->arcs[0] = n->arcs[0]; /* case exit */
  278.     new->arcs[1] = node_count - 1; /* case stmt. */
  279.     node_array[node_count - 1] = n;
  280.     node_array[v] = new;
  281.  
  282.     /* and add some case labels */
  283.     for ( i = 1; i < n->num_arcs; i++ ) {
  284.         new = get_node( 1 );
  285.         new->node_type = N_CASELAB;
  286.         new->num_arcs = 1;
  287.         new->arcs[0] = n->arcs[i];
  288.         n->arcs[i] = node_count - 1;
  289.         new->varpart[V_CASESLOT] = i - 1 + n->varpart[V_BASE];
  290.         node_array[node_count - 1] = new;
  291.     }
  292.     }
  293.  
  294.  skip_else:
  295.     node_array[v]->node_scratch = FINISHED;
  296. }
  297.  
  298. static struct node *
  299. get_orif( a_pred, a_negate, b_pred, b_negate, then_arc, else_arc )
  300. int a_pred;
  301. int a_negate;
  302. int b_pred;
  303. int b_negate;
  304. int then_arc;
  305. int else_arc;
  306. {
  307.     register struct node *n;
  308.  
  309.     if ( node_count + 1 > node_max )
  310.     node_grow();
  311.  
  312.     n = get_node( 2 );
  313.     n->node_type = N_ORIF;
  314.     n->num_arcs = 2;
  315.     n->arcs[THEN_ARC] = then_arc;
  316.     n->arcs[ELSE_ARC] = else_arc;
  317.     n->varpart[V_NEGATE] = FALSE;
  318.     n->varpart[V_PRED1] = node_count - 1; /* this will be a_pred */
  319.  
  320.     if ( a_negate )
  321.     node_array[a_pred]->varpart[V_NEGATE] =
  322.         ! node_array[a_pred]->varpart[V_NEGATE];
  323.  
  324.     n->varpart[V_PRED2] = b_pred;
  325.  
  326.     if ( b_negate )
  327.     node_array[b_pred]->varpart[V_NEGATE] =
  328.         ! node_array[b_pred]->varpart[V_NEGATE];
  329.  
  330.     return n;
  331. }
  332.  
  333. /*
  334.  * using depth first search, mark back edges using mark_edge,
  335.  * and nodes entered by back edges using MARK
  336.  */
  337. static
  338. search( v )
  339. register int v;
  340. {
  341.     register int adj;
  342.     register int i;
  343.     register struct node *n;
  344.  
  345.     n = node_array[v];
  346.     n->node_scratch = STACKED;
  347.  
  348.     for (i = 0; i < n->num_arcs; i++) {
  349.     adj = n->arcs[i];
  350.  
  351.     if ( node_array[adj]->node_scratch == UNSEEN )
  352.         search( adj );
  353.  
  354.     else if ( node_array[adj]->node_scratch == STACKED ) {
  355.  
  356.         /* mark adj node as entered by back edge */
  357.         mark( node_array[adj] );
  358.         /* mark edge as being back edge */
  359.         mark_edge( n->arcs[i] );
  360.     }
  361.     }
  362.     n->node_scratch = FINISHED;
  363.     access_count += 1;
  364. }
  365.  
  366. /*
  367.  * mark unreachable nodes.  Don't change N_IF nodes if they are
  368.  * unreachable--we need the type information later.
  369.  */
  370. static
  371. unreach()
  372. {
  373.     int v;
  374.  
  375.     for ( v = 0; v < node_count; v++ )
  376.     if ( node_array[v]->node_scratch == UNSEEN &&
  377.         node_array[v]->node_type != N_IF &&
  378.         node_array[v]->node_type != N_ORIF )
  379.  
  380.         node_array[v]->node_type = N_UNREACH;
  381. }
  382.  
  383. /* add N_LOOP, N_ITER at nodes entered by back edges, and adjust edges */
  384. addloop()
  385. {
  386.     register int v;
  387.     register int adj;
  388.     register int j;
  389.     register int oldnum;
  390.     register struct node *n, *loop, *iter;
  391.  
  392.     /* insloop increases node_count */
  393.  
  394.     for (v = 0, oldnum = node_count; v < oldnum; ++v) {
  395.  
  396.     n = node_array[v];
  397.  
  398.     if ( marked(n) ) {
  399.         /* remove mark indicating v entered by back edge */
  400.         unmark(n);
  401.  
  402.         if ( node_count + 2 >= node_max )
  403.         node_grow();
  404.  
  405.         /* add N_LOOP, N_ITER since v entered by back edge*/
  406.         loop = get_node( 1 );
  407.         loop->node_type = N_LOOP;
  408.         loop->num_arcs = 1;
  409.  
  410.         iter = get_node( 1 );
  411.         iter->node_type = N_ITER;
  412.         iter->num_arcs = 1;
  413.  
  414.         access_count += 2;
  415.  
  416.         /* want N_LOOP to take on node number v, so that arcs other than
  417.            back arcs entering v will enter N_LOOP */
  418.  
  419.         node_array[v] = loop;
  420.         node_array[node_count-2] = iter;
  421.         node_array[node_count-1] = n;
  422.  
  423.         loop->arcs[0] = node_count - 2;
  424.         iter->arcs[0] = node_count - 1;
  425.         iter->varpart[V_FATHER] = v;
  426.     }
  427.     }
  428.  
  429.     /* arcs which used to enter v now enter N_LOOP;
  430.      * must make back edges enter N_ITER */
  431.  
  432.     for (v = 0; v < node_count; ++v)
  433.     for ( j = 0; j < node_array[v]->num_arcs; ++j ) {
  434.  
  435.         if ( marked_edge( node_array[v]->arcs[j] ) ) {
  436.  
  437.         unmark_edge( node_array[v]->arcs[j] );
  438.         adj = node_array[v]->arcs[j];
  439.  
  440.         if ( node_array[adj]->node_type != N_ITER )
  441.             /* change arc to point to N_ITER */
  442.             node_array[v]->arcs[j] = node_array[adj]->arcs[0];
  443.         }
  444.     }
  445. }
  446.  
  447. /* repeat df search in order to fill in after, ntoaft, ntobef tables */
  448. static
  449. repsearch(v)
  450. register int v;
  451. {
  452.     register int adj;
  453.     register int i, temp;
  454.  
  455.     ntobef(v) = befcount;
  456.     befcount++;
  457.  
  458.     for ( i = 0; i < node_array[v]->num_arcs; i++ ) {
  459.     adj = node_array[v]->arcs[i];
  460.     if ( ntobef(adj) == NONE )
  461.         repsearch( adj );
  462.     }
  463.  
  464.     aftcount++;
  465.     temp = access_count - aftcount;
  466.     after(temp) = v;
  467.     ntoaft(v) = temp;
  468. }
  469.  
  470.  
  471. /* define ANC(v,w) true if v == w or v is ancestor of w (reflexive ancestor) */
  472. #define ANC(v,w) ( ntobef(v) <= ntobef(w) && ntoaft(v) <= ntoaft(w) )
  473.  
  474. /*
  475.  * set head(v) to N_ITER heading smallest loop containing v, for each v
  476.  */
  477.  
  478. /*
  479.  * Search nodes in reverse of after numbering so that all paths from
  480.  * a node to an ancestor are searched before the node.
  481.  *
  482.  * At any point, the current value of head allows chains of nodes
  483.  * to be reached from any node v by taking head(v), head(head(v)), etc.
  484.  * until an NONE value is reached.  Upon searching each arc, 
  485.  * the appropriate chains must be merged to avoid losing information.
  486.  *
  487.  * For example, from one path out of a node v it may be known that
  488.  * v is in a loop headed by z, while from another
  489.  * it may be known that v is in a loop headed by w.
  490.  * Thus, head(v) must be set to whichever of z,w is the closer ancestor,
  491.  * and the fact that this node is in a loop headed by the other must be
  492.  * recorded in head.
  493.  */
  494. static
  495. gethead()
  496. {
  497.     register int v, w, adj;
  498.     register int i, j;
  499.  
  500.     for (v = 0; v < node_count; ++v)
  501.     head(v) = NONE;
  502.  
  503.     for (i = access_count -1; i >= 0; i--) {
  504.     v = after(i);
  505.  
  506.     for (j = 0; j < node_array[v]->num_arcs; ++j) {
  507.         adj = node_array[v]->arcs[j];
  508.  
  509.         if ( ntoaft(adj) < i ) /* back edge */
  510.         merge( v, adj );
  511.  
  512.         else if ( ANC(v, adj) ) { /* not back edge or cross edge */
  513.         /*
  514.          * need to do only tree edges - must not do edge (v,adj)
  515.          * when head(adj) is not ANC of v
  516.          */
  517.         if ( DEFINED(head(adj)) && ANC(head(adj),v) )
  518.             merge( v, head(adj) );
  519.  
  520.         } else {        /* cross edge */
  521.  
  522.         w = lowanc( adj, v );
  523.         if ( DEFINED(w) )
  524.             merge( w, v );
  525.         }
  526.     }
  527.     if ( node_array[v]->node_type == N_LOOP )
  528.         /* head of N_ITER must be different N_ITER */
  529.         head(node_array[v]->arcs[0]) = head(v);
  530.     }
  531. }
  532.  
  533.  
  534. /* find the first node in chain of y which is anc of z, if it exists */
  535. static int
  536. lowanc( y, z )
  537. register int y, z;
  538. {
  539.     while ( y != -1 && !ANC(y,z) )
  540.     y = head(y);
  541.  
  542.     return y;
  543. }
  544.  
  545.  
  546. /* merge chains of w and y according to ANC relation */
  547. static
  548. merge( w, y )
  549. int w, y;
  550. {
  551.     int t, min;
  552.  
  553.     if ( w == y )
  554.     return;
  555.  
  556.     if ( ANC(w,y) ) {        /* set t to min of w,y */
  557.     t = y;
  558.     y = head(y);
  559.     } else {
  560.     t = w;
  561.     w = head(w);
  562.     }
  563.  
  564.     /* construct chain at t by adding min of remaining elements */
  565.  
  566.     while (w != -1 && y != -1) {
  567.     if ( ANC(w,y) ) {
  568.         min = y;
  569.         y = head(y);
  570.     } else {
  571.         min = w;
  572.         w = head(w);
  573.     }
  574.  
  575.     if ( t != min ) {
  576.         head(t) = min;
  577.         t = min;
  578.     }
  579.     }
  580.  
  581.     if ( w == -1 )
  582.     min = y;
  583.     else
  584.     min = w;
  585.  
  586.     if ( t != min )
  587.     head(t) = min;
  588. }
  589.  
  590.  
  591. /*
  592.  * find forward in-arcs for each node, pretending that arcs which jump
  593.  * into a loop jump to the head of the largest such loop instead, based
  594.  * on the depth first search tree
  595.  */
  596.  
  597. /* construct array "inarc" containing in arcs for each node */
  598. static
  599. getinarc()
  600. {
  601.     register int v, adj, x;
  602.     register int i, j;
  603.  
  604.     for (v=0; v < node_count; v++)
  605.     inarc(v) = 0;
  606.  
  607.     /* fill in inarc nodes */
  608.  
  609.     for (i = 0; i < access_count; ++i) {
  610.     v = after(i);
  611.  
  612.     for (j = 0; j < node_array[v]->num_arcs; ++j) {
  613.         adj = node_array[v]->arcs[j];
  614.  
  615.         /* not a back edge */
  616.         /* if edge jumps into loop, pretend jumps to head of
  617.            largest loop jumped into */
  618.  
  619.         if ( ntoaft(adj) > ntoaft(v) ) {
  620.         x = maxentry( v, adj );
  621.         if ( !DEFINED(x) )
  622.             x = adj;
  623.         else
  624.             x = node_array[x]->varpart[V_FATHER];
  625.  
  626.         /* insert v in list inarc[x] */
  627.         inarc(x) = consls( v, inarc(x) );
  628.         }
  629.     }
  630.     }
  631. }
  632.  
  633. /* return z if z is N_ITER of largest loop containing y but not x,
  634.    NONE otherwise */
  635. static int
  636. maxentry( x, y )
  637. int x, y;
  638. {
  639.     if ( head(y) == NONE )
  640.     return(NONE);
  641.  
  642.     if ( loomem( x, head(y) ) )
  643.     return (NONE);
  644.  
  645.     y = head(y);
  646.  
  647.     while ( head(y) != NONE ) {
  648.     if ( loomem( x, head(y) ) )
  649.         return(y);
  650.  
  651.     y = head(y);
  652.     }
  653.  
  654.     return(y);
  655. }
  656.  
  657. /* return TRUE if x is in loop headed by y, FALSE otherwise */
  658. static int
  659. loomem( x, y )
  660. register int x, y;
  661. {
  662.     register int w;
  663.  
  664.     if ( !DEFINED(y) )
  665.     return TRUE;
  666.  
  667.     w = (node_array[x]->node_type == N_ITER) ? x : head(x);
  668.  
  669.     for ( ; DEFINED(w); w = head(w) )
  670.     if ( w == y )
  671.         return TRUE;
  672.  
  673.     return FALSE;
  674. }
  675.  
  676.  
  677. /*
  678.  * set dom(v) to immediate dominator of v, based on arcs as stored in inarcs
  679.  * (i.e. pretending the graph is reducible if it isn't).
  680.  * Algorithm is from Hecht and Ullman, Analysis of a simple algorithm for
  681.  * global flow analysis problems, except bit vector operations replaced by
  682.  * search through DOM to save quadratic blowup in space 
  683.  */
  684. static
  685. getdom()
  686. {
  687.     register int v;
  688.     register int i;
  689.     register struct list *ls;
  690.  
  691.     for (v = 0; v < node_count; ++v)
  692.     dom(v) = NONE;
  693.  
  694.     for (i = 1; i < access_count; ++i) {
  695.     v = after(i);
  696.     for (ls = inarc(v); ls; ls = ls->next_list) {
  697.         dom(v) = comdom( dom(v), ls->element );
  698.     }
  699.     }
  700. }
  701.  
  702. /* find closest common dominator of u,v */
  703. static int
  704. comdom( u, v )
  705. register int u, v;
  706. {
  707.     if (u == NONE)
  708.     return(v);
  709.  
  710.     if (v == NONE)
  711.     return(u);
  712.  
  713.     while(u != v) {
  714.     if (ntoaft(u) < ntoaft(v))    
  715.         v = dom(v);
  716.     else
  717.         u = dom(u);
  718.     }
  719.  
  720.     return(u);
  721. }
  722.  
  723. /*
  724.  * use inarc, dom, and head to build tree representing structure of program.
  725.  *    Each node v has children denoted by
  726.  *    node_array[v]->child[0], node_array[v]->child[1], ...
  727.  *    representing code nested within v
  728.  *
  729.  *    node_array[v]->right_sibling is right sibling of v or NONE,
  730.  *    and represents code following v at the same level of nesting,
  731.  */
  732.  
  733. /* build tree */
  734. static
  735. gettree()
  736. {
  737.     register int v, u, from;
  738.     register int i;
  739.     register int found;
  740.     register struct node *from_node;
  741.  
  742.     for ( v = 0; v < node_count; ++v ) {
  743.     node_array[v]->right_sibling = NONE;
  744.  
  745.     for ( i = 0; i < CHILDNUM(v); ++i )
  746.         node_array[v]->child[i] = NONE;
  747.     }
  748.  
  749.     for (i = access_count-1; i > 0; --i) {
  750.     v = after(i);
  751.     found = FALSE;
  752.  
  753.     /* the unique element of inarc(v) or NONE */
  754.     from = one_element( inarc(v) );
  755.  
  756.     if ( DEFINED(from) ) {
  757.  
  758.         from_node = node_array[from];
  759.  
  760.         if ( ( from_node->node_type == N_BRANCH ||
  761.           from_node->node_type == N_IF ||
  762.           from_node->node_type == N_ORIF ) &&
  763.         ( head(v) == head(from) || asoc( v, exit_size ) != -1 ) ) {
  764.  
  765.         /*
  766.          * place in clause of N_BRANCH, N_[OR]IF if in smallest loop
  767.          * containing it or if size of code for v is <= exit_size
  768.          */
  769.  
  770.         if ( from_node->arcs[THEN_ARC] == v ) {
  771.             from_node->child[THEN_ARC] = v;
  772.             found = TRUE;
  773.  
  774.         } else {
  775.             from_node->child[ELSE_ARC] = v;
  776.             found = TRUE;
  777.         }
  778.  
  779.         } else if ( node_array[v]->node_type == N_ITER ||
  780.              from_node->node_type == N_ITER ) {
  781.  
  782.         /* N_LOOP -> N_ITER -> BODY always in same loop */
  783.         from_node->child[0] = v;
  784.         found = TRUE;
  785.  
  786.         } else if ( node_array[from]->node_type == N_SWITCH ) {
  787.  
  788.         if ( from_node->arcs[1] == v ) {
  789.             from_node->child[0] = v;
  790.             found = TRUE;
  791.         }
  792.         }
  793.     }
  794.  
  795.     if ( found )
  796.         continue;
  797.  
  798.     if ( loomem( v, head(dom(v)) ) ) {
  799.  
  800.         /* v is in smallest loop containing dom(v) */
  801.         insib( dom(v), v );
  802.  
  803.     } else {
  804.  
  805.         /*
  806.          * make v follow N_LOOP heading largest loop
  807.          * containing dom(v) but not v
  808.          */
  809.  
  810.         for ( u = head(dom(v)); head(u) != head(v); u = head(u) )
  811.         ;
  812.         insib( node_array[u]->varpart[V_FATHER], v );
  813.     }
  814.     }
  815. }
  816.  
  817. /*
  818.  * make right_sibling[w] = v, and make
  819.  * right_sibling[ rightmost sibling of v ] = previous right_sibling[w]
  820.  */
  821. static
  822. insib( w, v )
  823. register int w, v;
  824. {
  825.     register int u, temp;
  826.  
  827.     temp = node_array[w]->right_sibling;
  828.     node_array[w]->right_sibling = v;
  829.     for ( u = v; DEFINED(node_array[u]->right_sibling);
  830.      u = node_array[u]->right_sibling )
  831.     ;
  832.  
  833.     node_array[u]->right_sibling = temp;
  834. }
  835.  
  836. /* return # of nodes associated with v if <= n, -1 otherwise */
  837. static
  838. asoc( v, n )
  839. register int v;
  840. register int n;
  841. {
  842.     register int count, i, temp;
  843.     register int w;
  844.  
  845.     i = node_array[v]->node_type;
  846.     if ( i == N_FLOW || i == N_IF || i == N_BRANCH || i == N_SWITCH ||
  847.     i == N_END )
  848.     count = node_array[v]->end_address - node_array[v]->start_address;
  849.     else
  850.     count = 1;
  851.  
  852.     for ( i = 0; i < CHILDNUM(v); ++i ) {
  853.     w = node_array[v]->child[i];
  854.     if ( !DEFINED(w) )
  855.         continue;
  856.  
  857.     temp = asoc( w, n-count );
  858.     if ( temp == -1 )
  859.         return -1;
  860.  
  861.     count += temp;
  862.     if ( count > n )
  863.         return -1;
  864.     }
  865.  
  866.     if ( DEFINED(node_array[v]->right_sibling) ) {
  867.     temp = asoc( node_array[v]->right_sibling, n - count );
  868.     if ( temp == -1 )
  869.         return -1;
  870.     count += temp;
  871.     }
  872.  
  873.     if ( count > n )
  874.     return -1;
  875.     else
  876.     return count;
  877. }
  878.  
  879. /*
  880.  * list manipulation functions
  881.  */
  882.  
  883. /* make a list, insert it in front of ls */
  884. static struct list *
  885. consls( v, ls )
  886. register int v;
  887. register struct list *ls;
  888. {
  889.     register struct list *temp;
  890.  
  891.     temp = (struct list *) malloc( sizeof(struct list) );
  892.     temp->element = v;
  893.     temp->next_list = ls;
  894.     return temp;
  895. }
  896.  
  897. /* free a list */
  898. static
  899. freelst( ls )
  900. register struct list *ls;
  901. {
  902.     if ( ls == NULL )
  903.     return;
  904.  
  905.     if ( ls->next_list != NULL )
  906.     freelst( ls->next_list );
  907.  
  908.     free( ls );
  909. }
  910.  
  911. /* return element only if it is only element in list */
  912. static int
  913. one_element( ls )
  914. register struct list *ls;
  915. {
  916.     if ( ls == NULL )
  917.     return NONE;
  918.  
  919.     if ( ls->next_list )
  920.     return NONE;
  921.  
  922.     return ls->element;
  923. }
  924.